package com.longshine.arthmetic.tree;

import com.longshine.arthmetic.ColorNode;
import com.longshine.arthmetic.DrawableApp;
import com.longshine.arthmetic.Node;

/**
 * 红黑树 性质１:每个结点要么是红色，要么是黑色 性质２:根结点 为黑色 性质３：叶子结点为空，且为黑色
 * 性质４：红色结点的子结点为黑色，不能有两个连续的红结点 性质５：每条路径的黑色结点数相同
 * 
 * 
 * @classname ReadBlackTree.java
 * @author YitianC
 * @version Revision: 1.1, Date: 2008/05/14 01:43:47
 * @history Mar 13, 2012 6:59:16 PM
 * 
 */
public class ReadBlackTree extends SortTree {


	@Override
	public void addNode(Node n) {
		super.addNode(n);
		fixAfterInsertTree((ColorNode) n);
		((ColorNode) root).color = ColorNode.BLACK;
	}

	public boolean isBlack(ColorNode cn) {
		if (cn != null && cn.color == ColorNode.BLACK) {
			return false;
		}
		return true;
	}

	public void fixAfterInsertTree(ColorNode cn) {
		if (cn.weight == 11) {
			System.out.println("dsfsdf");
		}
		// 新结点是树的根结点, cn为黑色
		if (cn.parent == null) {
			cn.color = ColorNode.BLACK;
			return;
		}
		// 新结点的父结点为黑色，新结点为红色，保持性质5
		if (!cn.getParent().isRad()) {
			cn.color = ColorNode.RED;
			return;
		}
		// 父结点p和父结点的兄弟u结点都是红色, 将p,u置为黑色，p,u父结点g置为红色,重新修复g
		ColorNode u = cn.getParent().getBrother();
		if (cn.getParent().color == ColorNode.RED && u != null
				&& u.color == ColorNode.RED) {
			cn.getParent().color = ColorNode.BLACK;
			u.color = ColorNode.BLACK;
			cn.getParent().getParent().color = ColorNode.RED;
			this.fixAfterInsertTree(cn.getParent().getParent());
			return;
		}
		// 父结点p是红色，p兄弟结点u是黑色或缺少；且新结点是p的右结点，而p又是其父结点g的左子结点--左旋转
		else if (cn.getParent().color == ColorNode.RED
				&& (cn.getParent().getBrother() == null || cn.getParent()
						.getBrother().color == ColorNode.BLACK)) {
			ColorNode p = cn.getParent();
			ColorNode g = cn.getParent().getParent();
			if (cn == cn.getParent().right
					&& cn.getParent().getParent().left == cn.getParent()) {
				// 左旋转
				this.rotateLeft(p);
				this.fixAfterInsertTree(p);
			} else if (cn == cn.getParent().right
					&& cn.getParent().getParent().right == cn.getParent()) {
				// 右旋转
				this.rotateRight(p);
				this.fixAfterInsertTree(p);
			} else if (cn == cn.getParent().left
					&& cn.getParent().getParent().left == cn.getParent()) {
				// 右旋转
				cn.getParent().getParent().color = ColorNode.RED;
				cn.getParent().color = ColorNode.BLACK;
				this.rotateRight(g);
				// this.fixAfterInsertTree(g);
			} else if (cn == cn.getParent().left
					&& cn.getParent().getParent().right == cn.getParent()) {
				// 左旋转
				cn.getParent().getParent().color = ColorNode.RED;
				cn.getParent().color = ColorNode.BLACK;
				this.rotateLeft(g);
				// this.fixAfterInsertTree(g);
			}

		}

	}

	public void rotateLeft(ColorNode cn) {
		ColorNode p = cn.getParent();
		ColorNode r = cn.getRight();
		if (r == null)
			return;
		ColorNode t = r.getLeft();

		if (p != null) {
			if (p.left == cn) {
				p.left = r;
			} else {
				p.right = r;
			}
		} else {
			root = r;
		}
		r.left = cn;
		cn.parent = r;
		cn.right = t;
		if (t != null) {
			t.parent = cn;
		}
		r.parent = p;

	}

	public void rotateRight(ColorNode cn) {
		Node p = cn.parent;
		Node n1 = cn.left;
		if (n1 == null)
			return;
		Node n3 = cn.left.right;

		if (p != null) {
			if (p.left == cn) {
				p.left = n1;
			} else {
				p.right = n1;
			}
		} else {
			root = n1;
		}
		n1.parent = p;
		n1.right = cn;
		cn.parent = n1;
		cn.left = n3;
		if (n3 != null) {
			n3.parent = cn;
		}
	}
	@Override
	public void remove(Node rn) {
		ColorNode cn = (ColorNode)rn;
		if (cn.left != null && cn.right != null) {
			Node s = cn.left;
			while (s.right != null) {
				s = s.right;
			}
			cn.weight = s.weight;
			cn = (ColorNode) s;
		}
		ColorNode replace = cn.getLeft() == null ? cn.getRight() : cn.getLeft();
		if (replace != null) {
			replace.parent = cn.parent;
			// cn为根结点
			if (cn.parent == null) {
				root = replace;
			}
			// CN为左结点
			else if (cn == cn.parent.left) {
				cn.parent.left = replace;
			}
			// 右结点
			else {
				cn.parent.right = replace;
			}
			// 删除结点cn
			cn.parent = cn.left = cn.right = null;
			if (cn.color == ColorNode.BLACK) {
				//fixAfterDelete(replace);
				deleteCase1(replace);
			}
		}
		// cn为根结点
		else if (cn.parent == null) {
			root = null;
		} else {
//			System.out.println("有误");
			if(cn.color = ColorNode.BLACK){
				this.deleteCase1(cn);
			}
			if(cn.getParent().getLeft()==cn){
				cn.getParent().left = null;
			}
			else{
				cn.getParent().right = null;
				
			}
			cn.parent = null;
		}
	}

	// cn为新根，什么都不做
	public void deleteCase1(ColorNode cn) {
		if (cn.parent != null) {
			deleteCase2(cn);
		}
	}

	// cn的兄弟结点为红色，对父结点左旋转
	public void deleteCase2(ColorNode cn) {
		ColorNode s = cn.getBrother();
		if (s != null) {
			if (s.color == ColorNode.RED) {
				cn.getParent().color = ColorNode.RED;
				s.color = ColorNode.BLACK;
				if (cn == cn.getParent().left) {
					this.rotateLeft(cn.getParent());
				} else {
					this.rotateRight(cn.getParent());
				}
			}
			deleteCase3(cn);
		} else {
			System.out.println("deleteCase2 s=null");
		}

	}

	// P,s,s的儿子为黑色,重绘s为红色
	public void deleteCase3(ColorNode cn) {
		ColorNode s = cn.getBrother();
		if (cn.getParent().color == ColorNode.BLACK
				&& s.color == ColorNode.BLACK
				&& s.getLeft().color == ColorNode.BLACK
				&& s.getRight().color == ColorNode.BLACK) {
			s.color = ColorNode.RED;
			deleteCase1(cn.getParent());
		} else {
			deleteCase4(cn);
		}
	}

	// s,s的儿子为黑色，P为红色,交换p,s颜色
	public void deleteCase4(ColorNode cn) {
		ColorNode s = cn.getBrother();
		if (cn.getParent().color == ColorNode.RED && s.color == ColorNode.BLACK
				&& s.getLeft().color == ColorNode.BLACK
				&& s.getRight().color == ColorNode.BLACK) {
			cn.getParent().color = ColorNode.BLACK;
			s.color = ColorNode.RED;
		} else {
			deleteCase5(cn);
		}
	}

	// s为黑色,s左儿子为红色，S右儿子为黑色，而n是它父亲的左儿子,对S做右旋转
	public void deleteCase5(ColorNode cn) {
		ColorNode s = cn.getBrother();
		if (s.color == ColorNode.BLACK) {
			if (cn == cn.getParent().left
					&& s.getRight().color == ColorNode.BLACK
					&& s.getLeft().color == ColorNode.RED) {
				s.color = ColorNode.RED;
				s.getLeft().color = ColorNode.BLACK;
				this.rotateRight(s);
			} else if (cn == cn.getParent().right
					&& s.getLeft().color == ColorNode.BLACK
					&& s.getRight().color == ColorNode.RED) {
				s.color = ColorNode.RED;
				s.getRight().color = ColorNode.BLACK;
				this.rotateLeft(s);
			}
		}
		deleteCase6(cn);
	}

	// s为黑色，S的右儿子为红色，而cn是它父亲的左儿子，对p做左旋
	public void deleteCase6(ColorNode cn) {
		ColorNode s = cn.getBrother();
		s.color = cn.getParent().color;
		cn.getParent().color = ColorNode.BLACK;
		if(cn ==cn.getParent().left){
			s.getRight().color = ColorNode.BLACK;
			this.rotateLeft(cn.getParent());
		}
		else{
			s.getLeft().color = ColorNode.BLACK;
			this.rotateRight(cn.getParent());
		}
	}

	public void fixAfterDelete(ColorNode cn) {
		cn.color = ColorNode.RED;

	}

	public static void main(String args[]) {
		ReadBlackTree t = new ReadBlackTree();
		ColorNode n = new ColorNode(20);
		t.addNode(n);
		n = new ColorNode(50);
		t.addNode(n);
		ColorNode n1 = n;
		n = new ColorNode(19);
		Node t1 = n;
		t.addNode(n);
		n = new ColorNode(15);
		t.addNode(n);
		n = new ColorNode(30);
		t.addNode(n);
		n = new ColorNode(17);
		t.addNode(n);
		n = new ColorNode(5);
		t.addNode(n);
		n = new ColorNode(3);
		t.addNode(n);
		n = new ColorNode(11);
		t.addNode(n);
		n = new ColorNode(60);
		t.addNode(n);
		n = new ColorNode(25);
		t.addNode(n);
		n = new ColorNode(21);
		t.addNode(n);
		n = new ColorNode(4);
		t.addNode(n);
		n = new ColorNode(9);
		t.addNode(n);
		n = new ColorNode(18);
		t.addNode(n);
		n = new ColorNode(7);
		t.addNode(n);
		// n = new ColorNode(22);
		// t.addNode(n);
		// n = new ColorNode(6);
		// t.addNode(n);
		// n = new ColorNode(8);
		// t.addNode(n);
		// n = new ColorNode(20);
		// t.addNode(n);
		// n = new ColorNode(17);
		// t.addNode(n);
		// n = new ColorNode(32);
		// t.addNode(n);
		// n = new ColorNode(35);
		// t.addNode(n);
		// n = new ColorNode(28);
		// t.addNode(n);
		// t.remove(t1);
		t.remove(n1);
		DrawableApp da = new DrawableApp();
		System.out.println("总结点数为" + da.getNodeCount(t));
		System.out.println("树高度为" + da.getTreeHeight(t));
		da.drawTree(t);
		System.out.println(t);

	}
}
